package org.example.datastructure.ch12;

public class DisJointSet {
    int[] father;
    public DisJointSet(int n){
        father = new int[n];
        for(int i=0;i<n;i++) father[i] = -1;
    }
    public int find(int x){
        if(father[x]<0) return x;
        father[x] = find(father[x]);
        return father[x];
    }

    public void union(int x,int y){
        int fx = find(x);
        int fy = find(y);
        if(fx==fy) return;
        if(father[fx]>father[fy]){
            father[fy] += father[fx];
            father[fx] = fy;
        }else{
            father[fx] += father[fy];
            father[fy] = fx;
        }
    }
}
